use std::collections::{HashMap, HashSet};

use serde::{Deserialize, Deserializer};

struct UnionFind {
    parent: HashMap<String, String>,
    rank: HashMap<String, usize>,
}

impl UnionFind {
    fn new() -> Self {
        UnionFind {
            parent: HashMap::new(),
            rank: HashMap::new(),
        }
    }
    #[inline]
    fn make_set(&mut self, item: String) {
        self.parent.insert(item.clone(), item.clone());
        self.rank.insert(item, 0);
    }
    #[inline]
    fn find(&mut self, item: &str) -> String {
        let parent = self.parent.get(item).unwrap().clone();
        if &parent != item {
            let root = self.find(&parent);
            self.parent.insert(item.to_string(), root.to_string());
            root
        } else {
            parent
        }
    }
    #[inline]
    fn union(&mut self, item1: &str, item2: &str) {
        let root1 = self.find(item1);
        let root2 = self.find(item2);

        if root1 != root2 {
            let rank1 = *self.rank.get(&root1).unwrap();
            let rank2 = *self.rank.get(&root2).unwrap();

            if rank1 < rank2 {
                self.parent.insert(root1, root2);
            } else {
                self.parent.insert(root2.clone(), root1.clone());
                if rank1 == rank2 {
                    self.rank.entry(root1).and_modify(|r| *r += 1);
                }
            }
        }
    }
}

type Cases = HashMap<String, Case>;

#[derive(Debug)]
struct Case {
    citys: Vec<Vec<String>>,
}

impl<'de> Deserialize<'de> for Case {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        deserializer.deserialize_map(Visitor)
    }
}

struct Visitor;
impl<'de> serde::de::Visitor<'de> for Visitor {
    type Value = Case;

    fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        formatter.write_str("")
    }

    fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
    where
        A: serde::de::MapAccess<'de>,
    {
        let mut citys = Vec::new();
        while let Some((key, mut value)) = map.next_entry::<String, Vec<String>>()? {
            value.push(key);
            citys.push(value);
        }
        Ok(Case { citys })
    }
}
fn count(case: &Case) -> i32 {
    let mut uf = UnionFind::new();
    case.citys.iter().for_each(|city| {
        city.iter().for_each(|c| {
            uf.make_set(c.clone());
        });
    });
    case.citys.iter().for_each(|city| {
        city.iter().skip(1).for_each(|c| {
            uf.union(&city[0], c);
        });
    });

    let mut count = 0;
    let mut set = HashSet::new();
    case.citys.iter().for_each(|city| {
        let root = uf.find(&city[0]);
        if set.insert(root.clone()) {
            count += 1;
        }
    });
    count
}

pub fn count_provinces() -> String {
    let input = r#"{
    "1": {
        "成都": ["宜宾", "自贡", "绵阳", "泸州"],
        "桃园": ["台北", "高雄", "台中"],
        "东莞": ["深圳", "广州", "佛山"],
        "深圳": ["广州", "佛山", "东莞", "湛江"],
        "宜宾": ["泸州", "成都", "自贡", "绵阳"],
        "湛江": ["佛山", "广州", "深圳"],
        "自贡": ["成都", "宜宾", "泸州", "自贡"],
        "高雄": ["台南", "台北", "台中"],
        "台北": ["台南", "台中", "桃园"],
        "台南": ["台中", "高雄", "台北"],
        "绵阳": ["成都", "宜宾", "自贡"]
    },
    "2": {
        "东莞": ["深圳", "广州", "佛山"],
        "宜昌": ["襄阳", "恩施", "武汉"],
        "台南": ["台中", "高雄", "台北"],
        "深圳": ["广州", "佛山", "东莞", "湛江"],
        "桃园": ["台北", "高雄", "台中"],
        "武汉": ["黄冈", "荆州", "宜昌", "武汉"]
    },
    "3": {
        "惠州": ["梅州"],
        "南昌": ["九江", "新余"],
        "惠州": ["惠州"],
        "宜春": ["新余", "赣州"],
        "梅州": ["揭阳", "广州"],
        "汕头": ["潮州", "广州"],
        "南昌": ["宜春"],
        "赣州": ["新余", "吉安"],
        "汕头": ["汕尾", "广州", "深圳"]
    },
    "4": {
        "青浦": ["嘉定", "青浦"],
        "杭州": ["金华", "温州", "温州", "温州"],
        "上海": ["浦东", "青浦"],
        "台州": ["金华", "杭州", "丽水"],
        "闵行": ["松江", "金山", "青浦"]
    },
    "5": {
        "北京": ["房山"],
        "北京": ["大兴", "通州"],
        "北京": ["房山", "昌平"],
        "昌平": ["怀柔"]
    }
}"#;
    let cases: Cases = serde_json::from_str(input).unwrap();
    let mut result = Vec::with_capacity(cases.len());
    for i in 1..=cases.len() {
        result.push(count(cases.get(&i.to_string()).unwrap()).to_string());
    }
    result.join(",")
}
